package org.ziegler.algorithm.dijkstra;

import org.apache.commons.lang3.StringUtils;

import java.util.*;

/**
 * S --[6]--> A --[5]--> F
 * S --[2]--> B --[5]--> C --[2]--> F
 * B --[3]--> A
 * A --[1]--> C
 *
 * result: f > c > a > b > s >
 * @author Ziegler
 * date : 2021/5/5 19:18
 */

public class DSearch {

    private Map<String, Map<String, Integer>> graph = new HashMap<>();
    private Map<String, Integer> costs = new HashMap<>();
    private Map<String, String> parents = new HashMap<>();
    private Set<String> processed = new HashSet<>();


    public static void main(String[] args) {
        DSearch dSearch = new DSearch();
        dSearch.init();
        dSearch.start();
        dSearch.printResult();
    }

    private void printResult() {
        String parent = parents.getOrDefault("f", "");
        System.out.print("result: f > ");
        while (StringUtils.isNotEmpty(parent)) {
            System.out.print(parent + " > ");
            parent = parents.getOrDefault(parent, "");
        }
    }

    private String findLowestCostNode() {
        int lowestCost = Integer.MAX_VALUE;
        String lowestNode = "";
        for (Map.Entry<String, Integer> entry : costs.entrySet()) {
            String node = entry.getKey();
            Integer cost = entry.getValue();
            if (cost < lowestCost && !processed.contains(node)) {
                lowestCost = cost;
                lowestNode = node;
            }
        }
        return lowestNode;
    }

    private void start() {
        String lowestCostNode = findLowestCostNode();
        while (StringUtils.isNotEmpty(lowestCostNode)) {
            Integer cost = costs.get(lowestCostNode);
            Map<String, Integer> neighbors = graph.getOrDefault(lowestCostNode, Collections.emptyMap());
            for (Map.Entry<String, Integer> entry : neighbors.entrySet()) {
                String neighbor = entry.getKey();
                int newCost = cost + entry.getValue();
                if (costs.getOrDefault(neighbor, 0) > newCost) {
                    costs.put(neighbor, newCost);
                    parents.put(neighbor, lowestCostNode);
                }
            }
            processed.add(lowestCostNode);
            lowestCostNode = findLowestCostNode();
        }
    }

    private void init() {
        addNode("s", "a", 6);
        addNode("s", "b", 2);
        addNode("a", "c", 1);
        addNode("a", "f", 5);
        addNode("b", "a", 3);
        addNode("b", "c", 5);
        addNode("c", "f", 2);

        costs.put("a", 6);
        costs.put("b", 2);
        costs.put("c", Integer.MAX_VALUE);
        costs.put("f", Integer.MAX_VALUE);

        parents.put("a", "s");
        parents.put("b", "s");
        parents.put("f", "");
    }

    private void addNode(String from, String to, int cost) {
        graph.computeIfAbsent(from, s -> new HashMap<>()).put(to, cost);
    }

}
